package mao.leetcode.others.leetcode173;


import java.util.ArrayList;
import java.util.List;


class BSTIterator {
    List<Integer> list=new ArrayList<>();
    int index = 0;//访问下标
    public BSTIterator(TreeNode root) {
        TreeNode cur = root;
        TreeNode predecessor,temp;
        while (cur != null){
            if (cur.left == null){
                list.add(cur.val);
                cur=cur.right;
            }else {
                predecessor = cur.left;
                while (predecessor.right != null) predecessor =predecessor.right;
                predecessor.right = cur;

                temp=cur;
                cur=cur.left;
                temp.left=null; //断开原有连接，防止死循环
            }
        }
    }

    /** @return the next smallest number */
    public int next() {
        return list.get(index++);
    }

    /** @return whether we have a next smallest number */
    public boolean hasNext() {
        return index < list.size();
    }
}

